Teilbarkeit: 42 | (n^{7} - n) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeigen Sie: Für jede natürliche Zahl n ist [mm] $n^{7} [/mm] - n$ durch 42 teilbar. |
Hallo!
Eigentlich ist die Aufgabe im Zusammenhang mit Kongruenzen und chinesischer Restsatz gestellt worden... Mein Ansatz wäre aber folgender:
42 = 2*3*7
[mm] $n^{7}-n$
[/mm]
$= [mm] n*(n^{6}-1)$
[/mm]
$= [mm] n*(n^{3}-1)*(n^{3}+1)$
[/mm]
$= [mm] (n-1)*n*(n+1)*(n^{2}-n+1)*(n^{2}+n+1)$
[/mm]
D.h. der Term ist durch 2 und 3 teilbar, weil (n+1) oder n gerade ist, und weil bei drei aufeinanderfolgenden Zahlen (n-1)*n*(n+1) eine durch 3 teilbar sein muss.
Jetzt fehlt noch die 7, das hätte ich mit Induktion gemacht:
[mm] 7|n^{7}-n [/mm] gegeben.
[mm] 7|(n+1)^{7}-(n+1) [/mm] = [mm] (n^{7}-1)+7*(n^{6}+3n^{5}+5n^{4}+5n^{3}+3n^{2}+n)
[/mm]
also mit IV auch durch 7 teilbar.
Daran gefallen mir aber zwei Sachen nicht:
1. Dieser Lösungsweg hat wenig mit dem gerade in der Vorlesung behandeltem Stoff zu tun
2. Der Induktionsschritt mit dem Auflösen von [mm] (n+1)^{7} [/mm] ist aufwendig.
Deswegen die Frage: Gibt es noch einen anderen Weg, welcher Kongruenzen stärker mit einbindet. Die Aufsplittung 42 = 2*3*7 ist auch als Tipp in der Aufgabenstellung gegeben.
Danke für Eure Mühe,
Stefan.
|
|
| |
|
Du könntest nachweisen:
[mm] n^7\equiv n\mod{2}
[/mm]
[mm] n^7\equiv n\mod{3}
[/mm]
[mm] n^7\equiv n\mod{7}
[/mm]
...und Dich dann fragen, was das für [mm] n^7\mod{42} [/mm] heißt.
|
|
|
| |
|
Hallo!
Danke für deine Antwort!!!
Genau sowas meinte ich. Nun bin ich aber leider unerfahren in solchen Rechnungen, besonders wenn da nur Variablen stehen.
Ich verstehe, dass wenn [mm] $n^{7}-n$ [/mm] 42 teilen soll, die obigen Kongruenzen
[mm] $n^{7} [/mm] - n [mm] \equiv [/mm] 0 [mm] \mbox{ mod 2 } \gdw n^{7} \equiv [/mm] n [mm] \mbox{ mod 2 }$
[/mm]
[mm] $n^{7} [/mm] - n [mm] \equiv [/mm] 0 [mm] \mbox{ mod 3 } \gdw n^{7} \equiv [/mm] n [mm] \mbox{ mod 3 }$
[/mm]
[mm] $n^{7} [/mm] - n [mm] \equiv [/mm] 0 [mm] \mbox{ mod 7 } \gdw n^{7} \equiv [/mm] n [mm] \mbox{ mod 7 }$
[/mm]
gelten müssen. Nun nehme ich mir also die Gleichung
[mm] $n^{7} \equiv [/mm] n [mm] \mbox{ mod 2 }$
[/mm]
vor. Das klingt jetzt zwar doof, aber ich weiß absolut nicht was ich tun könnte.
Ich habe eine Regel
[mm] $c*a\equiv c*b\mbox{ mod k} [/mm] und ggT(c,k) = 1 [mm] \Rightarrow a\equiv [/mm] b [mm] \mbox{ mod k}$
[/mm]
Angewandt auf das Beispiel wäre c = n, a = [mm] n^{6} [/mm] und b = 1 und k = 2. Für ungerade n könnte ich folgern: ggT(n,2) = 1 und dann
[mm] $n^{6} \equiv [/mm] 1 [mm] \mbox{ mod 2 }$
[/mm]
wobei ich nicht weiß, was ich damit gewonnen habe... Jetzt steht da mehr oder weniger eine wahre Aussage, weil ja n ungerade vorausgesetzt wurde, aber...
Für gerade n gilt die Aussage ja auch logischerweise ??
Bei mod 3 und mod 7 habe ich auch nicht so wirklich einen Plan. Kann mir bitte nochmal jemand auf die Sprünge helfen?
Danke für Eure Hilfe!
Stefan.
|
|
|
| |
|
Hallo Stefan!
> Ich habe eine Regel
>
> [mm]c*a\equiv c*b\mbox{ mod k} und ggT(c,k) = 1 \Rightarrow a\equiv b \mbox{ mod k}[/mm]
>
> Angewandt auf das Beispiel wäre c = n, a = [mm]n^{6}[/mm] und b = 1
> und k = 2. Für ungerade n könnte ich folgern: ggT(n,2) = 1
> und dann
>
> [mm]n^{6} \equiv 1 \mbox{ mod 2 }[/mm]
>
> wobei ich nicht weiß, was ich damit gewonnen habe... Jetzt
> steht da mehr oder weniger eine wahre Aussage, weil ja n
> ungerade vorausgesetzt wurde, aber...
> Für gerade n gilt die Aussage ja auch logischerweise ??
Wieso das denn jetzt? Du betonst doch zweimal, dass Deine Regel hier nur für ungerade n angewandt werden kann...
> Bei mod 3 und mod 7 habe ich auch nicht so wirklich einen
> Plan. Kann mir bitte nochmal jemand auf die Sprünge
> helfen?
Ok.
Deine Regel ist hübsch, aber hier nicht so hilfreich.
Du brauchst den ![[]](/images/popup.gif) "kleinen Fermat".
Da 2,3 und 7 Primzahlen sind, folgt aus dem Satz unmittelbar die schon behauptete Restklassenkongruenz.
Nun gilt allgemein:
[mm] a\equiv b\mod{c} \wedge a\equiv b\mod{d}, \a{}ggT(c,d)=1 \Rightarrow a\equiv b\mod{(c*d)}
[/mm]
Damit kannst Du folgern [mm] n^7\equiv n\mod{(2*3*7)} \gdw n^7-n\equiv 0\mod{42} \gdw 42|(n^7-n) \forall n\in\IN
[/mm]
> Danke für Eure Hilfe!
> Stefan.
Gern. Grüße!
|
|
|
| |
|
Hallo!
> Du brauchst den
> "kleinen Fermat".
>
> Da 2,3 und 7 Primzahlen sind, folgt aus dem Satz
> unmittelbar die schon behauptete Restklassenkongruenz.
Aus dem kleinen Fermatschen Satz erhalte ich
[mm] n^{7} \equiv [/mm] n mod 7
Das kann ich ja sofort verwenden. Dann erhalte ich noch
[mm] n^{3} \equiv [/mm] n mod 3
[mm] n^{2} \equiv [/mm] n mod 2
das müsste ich jetzt ja irgendwie zu
[mm] n^{7} \equiv [/mm] n mod 3
[mm] n^{7} \equiv [/mm] n mod 2
machen... Ich weiß nicht, wie ich das hinbekommen könnte?
> Nun gilt allgemein:
> [mm]a\equiv b\mod{c} \wedge a\equiv b\mod{d}, \a{}ggT(c,d)=1 \Rightarrow a\equiv b\mod{(c*d)}[/mm]
>
> Damit kannst Du folgern [mm]n^7\equiv n\mod{(2*3*7)} \gdw n^7-n\equiv 0\mod{42} \gdw 42|(n^7-n) \forall n\in\IN[/mm]
>
> > Danke für Eure Hilfe!
> > Stefan.
> Gern. Grüße!
Danke für Eure (und Deine  ) Hilfe,
Stefan.
|
|
|
| |
|
Ach so. Ok, hier etwas kleinschrittiger:
> Aus dem kleinen Fermatschen Satz erhalte ich
>
> [mm]n^{7} \equiv[/mm] n mod 7
>
> Das kann ich ja sofort verwenden. Dann erhalte ich noch
>
> [mm]n^{3} \equiv[/mm] n mod 3
> [mm]n^{2} \equiv[/mm] n mod 2
>
> das müsste ich jetzt ja irgendwie zu
>
> [mm]n^{7} \equiv[/mm] n mod 3
> [mm]n^{7} \equiv[/mm] n mod 2
>
> machen... Ich weiß nicht, wie ich das hinbekommen könnte?
Genau. Das Ziel ist klar und Du hast es erkannt. So kommt man hin:
[mm] n^7=n^3*n^3*n\equiv n*n*n\equiv n^3\equiv n\mod{3}
[/mm]
[mm] n^7=n^2*n^2*n^2*n\equiv n*n*n*n\equiv n^2*n^2\equiv n*n\equiv n^2\equiv n\mod{2}
[/mm]
Naja, vielleicht doch nicht so unmittelbar wie behauptet.
|
|
|
| |
|
Hallo reverend,
danke für die Antwort! Sowas ähnliches hatte ich mir schon gedacht
Grüße, Stefan.
|
|
|
|
